/*********************************************
 * This class implements a* search. Info is passed from Agent
 * such as items we currently have. A priority queue is used to 
 * store potential states. This we we can remove the one with the
 * minimum heuristic first. The current heuristic is Manhattan distance,
 * quite basic but because it's admissible it does the job.
 * 
 * Due to the map not updating we had to keep track of locations
 * that have been blown up to avoid blowing up the same thing twice.
 * Not an issue with key/axe because we just open/chop again. Leads to redundant
 * moves but still guaranteed to get a solution. We also had to make sure we weren't
 * visiting the same dynamite spot and increasing our supplies of dynamite. We did this by
 * creating Dynamite/Item objects to keep track of dynamites picked up and items blown based on 
 * their location. States keep track of items available at each stage so backtracking can function.
 * 
 * Generating states is based on 3 cases. Forward, left or right. Chop/open/blow are treated
 * as an interim state to forward. If the state has not already been explored/going to be explored
 * add to the queue. States are deemed the same if they have the same location/items/destroyed the
 * same objects.
 * 
 */





import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;


public class GeniusSearch {

	public static final int homei = 80;
	public static final int homej = 80;
	
	public int currentPositioni = homei;
	public int currentPositionj = homej;
	
	private int currentGoali = homei;
	private int currentGoalj = homej;
		
	//potential future states
	private PriorityQueue<State> states;

	//	states already been to
	private LinkedList<State> visited; 

	//index 0 = the gold
	//index MAX = state right after the home state
	//in other words, this list is in reverse. Be careful when printing.
	private ArrayList<State> visitedStatesToGold;
	boolean found = false;
	/**
	 * This class implements the Genius Search
	 * The search that is very ingenious  
	 */
	public GeniusSearch() {

		visited = new LinkedList<State>();
		visitedStatesToGold = new ArrayList<State>();
	}
	
	//before the map is explored, can only use this in explored region.
	//trying to use this to go directly into fog of war will kill the program
	public boolean moveSearch(Map map, int agentDirection, boolean haveKey, boolean haveAxe,
							int numDynamites){
		//sort queue -lowest to highest heuristic
		Comparator<State> comparator = new heuristicComparator();
		states = new PriorityQueue<State>(11, comparator);
		State home = new State();
		home.setPrevious(null);
		home.setHeuristic(calculateH(currentPositioni, currentPositionj));
		home.setDirection(agentDirection);
		home.setPlace(currentPositioni, currentPositionj);
		
		home.setAxe(haveAxe);
		home.setKey(haveKey);
		ArrayList<Dynamite> haveDynamites = new ArrayList<Dynamite>();
		for (int i = 0; i < numDynamites; i++){
			Dynamite d = new Dynamite(9999,9999);
			haveDynamites.add(d);
		}
		home.setDynamites(haveDynamites);
		
		State s = null;

		//initial state
		states.add(home);

		//a*search
		while(!found && states.size() > 0) {
			s  = states.remove();
			if(s.i == currentGoali && s.j == currentGoalj) {
				found = true;

				//hit the gold, now find out how we got there
				State temp = s;
				while(temp != null && temp != home){
					visitedStatesToGold.add(temp);
					temp = temp.previous;
				}
			} else {
				if(!visited.contains(s)) {
					getStates(states, map, s, s.direction);
					visited.add(s);
				}
			}
		}
		//System.out.println(visitedStatesToGold);
		if (visitedStatesToGold.size() == 0){
			return false;
		} else {
			return true;
		}
	}

	public char returnMovesMadeToGetToGold(){
		char temp = ' ';
		if (visitedStatesToGold.size() > 0){
			temp = visitedStatesToGold.remove(visitedStatesToGold.size() - 1).move;
		}
		return temp;
	}

	private void getStates(PriorityQueue<State> states, Map m, State s,int dir) {
		State s1 = new State();
		State s2 = new State();
		State s3 = new State();

		s1.setPrevious(s);
		s1.setAxe(s.axe);
		s1.setKey(s.key);
		s1.changeDynamites(s.dynamites);
		s1.setUsed(s.used);
		s1.setDestroyed(s.destroyed);

		s2.setPrevious(s);
		s2.setAxe(s.axe);
		s2.setKey(s.key);
		s2.changeDynamites(s.dynamites);
		s2.setUsed(s.used);
		s2.setDestroyed(s.destroyed);

		s3.setPrevious(s);
		s3.setAxe(s.axe);
		s3.setKey(s.key);
		s3.changeDynamites(s.dynamites);
		s3.setUsed(s.used);
		s3.setDestroyed(s.destroyed);

		//3 possible options for each case (4 cases - current direction)

		if(dir == Map.LEFT) {
			s1.setHeuristic(calculateH(s.i, s.j-1));
			s1.setPlace(s.i, s.j-1);
			s1.setMove('f');
			s1.setDirection(Map.LEFT);
			s2.setHeuristic(calculateH(s.i, s.j));
			s2.setPlace(s.i, s.j);
			s2.setMove('l');
			s2.setDirection(Map.DOWN);
			s3.setHeuristic(calculateH(s.i, s.j));
			s3.setPlace(s.i, s.j);
			s3.setMove('r');
			s3.setDirection(Map.UP);

		} else if (dir == Map.UP) {
			s1.setHeuristic(calculateH(s.i-1, s.j));
			s1.setPlace(s.i-1, s.j);
			s1.setMove('f');
			s1.setDirection(Map.UP);
			s2.setHeuristic(calculateH(s.i, s.j));
			s2.setPlace(s.i, s.j);
			s2.setMove('l');
			s2.setDirection(Map.LEFT);
			s3.setHeuristic(calculateH(s.i, s.j));
			s3.setPlace(s.i, s.j);
			s3.setMove('r');
			s3.setDirection(Map.RIGHT);

		} else if (dir == Map.RIGHT) {
			s1.setHeuristic(calculateH(s.i, s.j+1));
			s1.setPlace(s.i, s.j+1);
			s1.setMove('f');
			s1.setDirection(Map.RIGHT);
			s2.setHeuristic(calculateH(s.i, s.j));
			s2.setPlace(s.i, s.j);
			s2.setMove('l');
			s2.setDirection(Map.UP);
			s3.setHeuristic(calculateH(s.i, s.j));
			s3.setPlace(s.i, s.j);
			s3.setMove('r');
			s3.setDirection(Map.DOWN);

		} else {
			s1.setHeuristic(calculateH(s.i+1, s.j));
			s1.setPlace(s.i+1, s.j);
			s1.setMove('f');
			s1.setDirection(Map.DOWN);
			s2.setHeuristic(calculateH(s.i, s.j));
			s2.setPlace(s.i, s.j);
			s2.setMove('l');
			s2.setDirection(Map.RIGHT);
			s3.setHeuristic(calculateH(s.i, s.j));
			s3.setPlace(s.i, s.j);
			s3.setMove('r');
			s3.setDirection(Map.LEFT);

		}


		if(m.getPosition(s1.i, s1.j) == 'a') {
			s1.setAxe(true);
		}
		if(m.getPosition(s1.i, s1.j) == 'k') {
			s1.setKey(true);
		}
		if(m.getPosition(s1.i, s1.j) == 'd') {
			if(s1.i == 79 && s1.j == 83 ) {
				System.out.println("hello");
			}
			s1.addDynamite(s1.i, s1.j);
		}


		if(m.getPosition(s1.i, s1.j) == 'T' && s1.axe) {
			State s0 = new State();
			s0.setPlace(s.i, s.j);
			s0.setHeuristic(s.heuristic);
			s0.setPrevious(s);
			s0.setMove('c');
			s0.setDirection(s1.direction);
			s1.setPrevious(s0);
			if(!(states.contains(s0) || visited.contains(s0))) {
				states.add(s0);
			}
			if(!(states.contains(s1) || visited.contains(s1))) {
				states.add(s1);
			} 
		} else if(m.getPosition(s1.i, s1.j) == 'T' && s1.dynamites.size() > 0) {
			Item i = new Item(s1.i, s1.j);
			if(s1.destroyed.contains(i)) {

			} else { 

				State s0 = new State();
				s0.setDestroyed(s.destroyed);
				

				s0.setPlace(s.i, s.j);
				s0.setHeuristic(s.heuristic);
				s0.setPrevious(s);
				s0.setMove('b');
				s0.destroyed.add(i);
				s0.changeDynamites(s.dynamites);
				s0.useDynamite();
				s0.setDirection(s1.direction); //probably should be s in terms of logic, clear this up later
				s0.setAxe(s.axe);
				s0.setKey(s.key);

				s1.setPrevious(s0);
				s1.destroyed.add(i);
				s1.useDynamite();
				if(!(states.contains(s0) || visited.contains(s0))) {
					states.add(s0);
				}

			}
			if(!(states.contains(s1) || visited.contains(s1))) {
				states.add(s1);
			} 
		}


		if(m.getPosition(s1.i, s1.j) == '-' && s1.key) {
			State s0 = new State();
			s0.setPlace(s.i, s.j);
			s0.setHeuristic(s.heuristic);
			s0.setPrevious(s);
			s0.setMove('o');
			s0.setDirection(s1.direction);
			s1.setPrevious(s0);
			if(!(states.contains(s0) || visited.contains(s0))) {
				states.add(s0);
			}
			if(!(states.contains(s1) || visited.contains(s1))) {
				states.add(s1);
			} 
		} else if(m.getPosition(s1.i, s1.j) == '-' && s1.dynamites.size() > 0) {
			Item i = new Item(s1.i, s1.j);
			if(s1.destroyed.contains(i)) {

			} else { 			
				State s0 = new State();
				s0.setDestroyed(s.destroyed);



				s0.setPlace(s.i, s.j);
				s0.setHeuristic(s.heuristic);
				s0.setPrevious(s);
				s0.setMove('b');
				s0.destroyed.add(i);
				s0.changeDynamites(s.dynamites);
				s0.useDynamite();
				s0.setDirection(s1.direction);
				s0.setAxe(s.axe);
				s0.setKey(s.key);


				s1.setPrevious(s0);
				s1.destroyed.add(i);
				s1.useDynamite();
				if(!(states.contains(s0) || visited.contains(s0))) {
					states.add(s0);
				}
			}
			if(!(states.contains(s1) || visited.contains(s1))) {
				states.add(s1);
			} 
		}


		if(m.getPosition(s1.i, s1.j) == '*' && s1.dynamites.size() > 0) {

			if(s1.i == 80 && s1.j == 83) {
				System.out.println("hello");
			}

			Item i = new Item(s1.i, s1.j);
			if(s1.destroyed.contains(i)) {

			} else { 



				State s0 = new State();
				s0.setDestroyed(s.destroyed);


				s0.setPlace(s.i, s.j);
				s0.setHeuristic(s.heuristic);
				s0.setPrevious(s);
				s0.setMove('b');
				s0.destroyed.add(i);
				s0.changeDynamites(s.dynamites);
				s0.useDynamite();
				s0.setDirection(s1.direction);
				s0.setAxe(s.axe);
				s0.setKey(s.key);

				s1.setPrevious(s0);
				s1.destroyed.add(i);
				s1.useDynamite();
				if(!(states.contains(s0) || visited.contains(s0))) {
					states.add(s0);
				}
			}
			if(!(states.contains(s1) || visited.contains(s1))) {
				states.add(s1);
			} 
		}
		
		/*
		
		//not needed
		Item i = new Item(s1.i, s1.j);
		if(s1.destroyed.contains(i)) {
			if(!(states.contains(s1) || visited.contains(s1))) {
				states.add(s1);
			} 
		}
*/
		if(!(m.getPosition(s1.i,s1.j) == '*' || m.getPosition(s1.i,s1.j)=='~' || m.getPosition(s1.i,s1.j)=='!'
				|| m.getPosition(s1.i,s1.j)=='-' || m.getPosition(s1.i,s1.j)=='T')) {
					


			if(!(states.contains(s1) || visited.contains(s1))) {
				states.add(s1);
			} 
		}
		if(!(states.contains(s2) || visited.contains(s2))) {
			states.add(s2);
		}
		if(!(states.contains(s3) || visited.contains(s3))) {
			states.add(s3);
		}

	}
	
	public void searchAgain(){
		this.found = false;
		visited = new LinkedList<State>();
	}
	
	public void setCurrentPosition(int i, int j){
		this.currentPositioni = i;
		this.currentPositionj = j;
	}
	
	public void setCurrentGoal(int i, int j){
		this.currentGoali = i;
		this.currentGoalj = j;
	}
	
	public boolean isAtCurrentGoal(){
		return (currentPositioni == currentGoali && currentPositionj == currentGoalj);
	}
	
	private int calculateH(int i, int j) {

		int result = Math.abs(currentGoali-i) + Math.abs(currentGoalj-j)
				   + Math.abs(currentPositioni-i) + Math.abs(currentPositionj-j);

		return result;
	}
	public void setGold(int i, int j) {
		this.currentGoali = i;
		this.currentGoalj = j;
	}
}
